\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{ulem}
\usepackage{wrapfig}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{\noindent{\bf Proof.}}{\hfill$\Box${\vspace*{\medskipamount}}}
\newcommand{\pbox}{\hfill$\Box${\vspace*{\medskipamount}}}

\title{Advanced Algorithms - Lecture notes}
\author{Prof. Bernard Moret, EPFL\\ typeset by: Valentina Sintsova, Javier Picorel, Vasileios Trigonakis}

\date{October 31, 2011}

\begin{document}

\maketitle

\thispagestyle{empty}
\pagestyle{empty}

%Valya's part
\section[]{Matching problem\footnote{End of theorem proof from the previous lecture.} }

The last two lectures were analysing the problem of finding the maximum matching on a graph.
\\\\
\textbf{Definition} (\textit{matching}). Given a graph $G=(V,E)$, the subset $M \subseteq E$ is a matching if and only if every pair of edges in $M$ is vertex disjoint. The size of the matching is naturally defined as the number of edges in it.\\

On the previous lecture we introduced the algorithm of finding maximum matching in a bipartite graph using breadth-first search (BFS) from every unmatched vertex which discovers multiple augmenting paths of the same length on each iteration.

We also proved a lemma which states that the lengths of successive shortest augmenting paths returned by this algorithm form a non-decreasing sequence. 

Now we need to end the proof of the following theorem started in the previous lecture:

\begin{theorem} Suppose we run this algorithm over the graph $G=(V,E)$ and it finds maximum matching $M$. Let $P_1$,$P_2$, $\dots$, $P_{\left| M \right|} $ be the sequence of augmenting paths found in turn by the algorithm.

Then the collection $\left| P_1\right|, \left| P_2\right| , \dots, \left| P_{\left| M \right|}\right| $ includes only $O\left(\sqrt{\left| M \right|} \right)$ distinct values.
\end{theorem}

\begin{proof}
%From the lemma proved at the previous lecture we know that the lengths of augmenting paths used by the algorithms create non-decreasing sequence. 
Let's define index $j = \left| M \right| - \sqrt{\left| M \right|}$ and then divide the collection  $\left| P_1\right|, \left| P_2\right| , \dots, \left| P_{\left| M \right|}\right| $ into two parts: one part before this index $j$ and one after.

By definition the second part contains $\left| M \right| - j =  \sqrt{\left| M \right|}$ elements, and thus, the number of distinct elements in it is obviously $O\left(\sqrt{\left| M \right|} \right)$.

Let's consider the first part. From the lemma we know that this sequence is non-decreasing, so the number of distinct elements in it is bounded by the value of the last element $\left| P_j\right|$. Let's find its maximum possible value, or, in other words, how long the path $ P_{\left| M \right| - \sqrt{\left| M \right|}}$ can be:

Because at $P_{\left| M \right| - \sqrt{\left| M \right|}}$ we know that we are $\sqrt{\left| M \right|}$ from the optimal solution $\left| M \right|$, there exist $\sqrt{\left| M \right|}$ vertex-disjoint augmenting paths (those are the paths from the second part of path sequence). Each augmenting path should use both edges from the current matching and the edges not in it. Considering only the edges which augmenting paths use from the existent matching, at most those paths together can use every single edge in it, i.e. $\left| M \right| - \sqrt{\left| M \right|}$ edges. What is the upper bound of length of the shortest path of them?  All following $\sqrt{\left| M \right|}$ paths will be not shorter than its length and, as was shown, the maximum number of edges they can use in total from current matching is not greater than $\left| M \right| - \sqrt{\left| M \right|}$. So the maximum possible number of edges from the existent matching in this shortest path is $\frac{\left| M \right| - \sqrt{\left| M \right|}}{\sqrt{\left| M \right|}}$.

Thus, as in augmenting path the edges from the existent matching should alternate with edges not in it, the shortest path among the following paths has maximum possible length of $2\left( \frac{\left| M \right| - \sqrt{\left| M \right|}}{\sqrt{\left| M \right|}}\right) +1 = 2 \sqrt{\left| M \right|} - 1$, or is $O(\sqrt{\left| M \right|})$.

So the length of $P_j$ is also $O(\sqrt{\left| M \right|})$, and the same is the number of distinct lengths in the first part.

As both parts of sequence have $O(\sqrt{\left| M \right|})$ distinct values, the overall number of distinct lengths is also $O(\sqrt{\left| M \right|})$, what was required to prove.
\end{proof}


As the number of iterations using the suggested BFS algorithm is exactly the number of distinct lengths of the augmenting paths, this theorem shows that problem of finding a maximum matching in a bipartite graph can be solved in $O(\sqrt{M^*}\left| E\right|)$ which is $O(\sqrt{\left| V\right|}\left| E\right|)$.

\vspace{10pt}

\section{Maximum-flow problem}

\subsection{Description}

Suppose we are given a network - an undirected graph $G=(V,E)$ with two special vertices (source $s$ and sink $t$) and a capacity function over the edges $c \colon E \to \mathbb{N}^+$.
\\\\
\textbf{Definition} (\textit{flow}). A flow is an assignment $f \colon V \times V \rightarrow \mathbb{N}$ to directed edges $(u,v)$ where $\{u,v\}\in E$ such that it satisfies the following constraints:
\begin{enumerate}
\item[i.] $\forall u \in V\quad u \not= s,t \quad \sum\limits_{\substack{
v \in V \text{ s.t. } \\
\{u,v\}\in E}} {f(u,v)} = 0 $ \hspace{43pt} --- \hspace{8 pt}conservation

\item[ii.] $\forall u,v \in V$ s.t. $\{u,v\}\in E \quad f(u,v) = - f(v,u)$ \hspace{10pt} --- \hspace{8 pt}skew symmetry
\item[iii.] $\forall u,v \in V$ s.t. $\{u,v\}\in E \quad \left|f(u,v) \right| \le c(\{u,v\})$
\end{enumerate}

Conservation constraint means that for any vertex, except of the source and the sink, incoming flow to a vertex equals to the outcoming flow from it. Skew symmetry means that flow in one direction is negative with respect to the flow in other direction. And the third constraint implies that capacity of each edge bounds the maximum value of flow through this edge in any direction.

\vspace{10pt}
The problem is to find the flow with maximum cost, where the cost of the flow is defined as $\sum\limits_{\substack{
u \in V \text{ s.t. } \\
\{u,t\}\in E}}{f(u,t)}$, that is the sum of the flow assignment to the edges incoming to the sink.

%Vasilis's part
\subsection{Algorithm I (augmenting paths)}
We will initially introduce an algorithm which uses augmenting paths for calculating the maximum network flow. This algorithm is not very efficient, thus is not the one that we will use in the end, but is a nice introduction to the problem.

In the context of network flow, an \textit{augmenting path} is a path from the source ($s$) to the sink ($t$) that has some ``free flow''. In other words, the path has some available capacity. 

The algorithm takes the following steps:
\begin{enumerate}
\item[i.] find an augmenting path $P$
\item[ii.] find the edge of $P$ with the minimum capacity; this is the maximum flow that the path can carry
\item[iii.] change the graph to reflect the allocation of flow on $P$
\end{enumerate}
These steps are repeated until there are no augmenting paths from $s$ to $t$.

\subsubsection*{Example}
We will use the following graph to illustrate the aforementioned algorithm. The numbers adjacent to the edges represent their capacity.\\

\begin{center}
\input{augmenting2.tex}
\end{center}

Assume that the first augmenting path considered is the one depicted in blue on the right figure. It should be clear that this path has capacity 1, since the edge with the minimum capacity in the path sets the limit. By allocating this capacity to the path, we change the capacities of every edge. Now there is an edge with capacity 0. What should we do with this edge?

A first idea would be to remove it, but this would be wrong, because this undirected link can be used to carry flow on the opposite direction. It initially had capacity 1, but since it now  carries 1 unit of flow towards a direction, it has a capacity of 2 towards the opposite direction.

Therefore, we will start considering the graph as directed and recalculate the (directed) capacities after each step.

\begin{center}
\input{augmenting3.tex}
\end{center}

On the left,  the graph with the directed edges and the recalculated capacities which reflect the allocation of flow is depicted. On the directed graph, one can use breadth first search (BFS) to find a new (shortest) path from $s$ to $t$. Consider that we select the augmenting path depicted on the right. As before, this path has a capacity of 1. Using it and recalculating the capacities produces the left graph below.

\begin{center}
\input{augmenting4.tex}
\end{center}

We use BFS on this graph once again and we find the last augmenting path illustrated on the right. After utilizing the capacity of this path, there exist no other paths from $s$ to $t$, hence the algorithm has completed.

\begin{center}
\input{augmenting5.tex}
\end{center}

To summarize, the algorithm finds an augmenting path, utilizes it, and redraws the graph until there are no more paths from $s$ to $t$. The adapted directed graphs used by the algorithm are called \textit{residual networks}.

We claim that this algorithm is optimal\footnote{it produces the maximum possible flow} and we will present and prove a theorem that verifies this statement.

\subsubsection*{Optimality}

\begin{theorem}
If the residual graph of the network $(G, s, t)$ with respect to flow $F$ has no path from $s$ to $t$, then $F$ is a maximum flow.
\label{theorem:maxflow}
\end{theorem}

Theorem \ref{theorem:maxflow} trivially verifies that the algorithm using augmenting paths gives an optimal solution. We will not proceed to the proof of Theorem \ref{theorem:maxflow}, since we will introduce and prove a stronger theorem later.
\\\\
\textbf{Definition} (\textit{cut}). Given a network $(G, s, t)$, a \textit{cut} in the network is a subset of edges $E' \subseteq E$, such that the subgraph $G' = (V, E-E')$ has no path from $s$ to $t$.
\\\\
Therefore, by the definition of cut, if we remove all edges in $E$, i.e., $E' \equiv E$, the $s$ and $t$ become ``disconnected''\footnote{there is no path from $s$ to $t$}.
\\\\
\textbf{Definition} (\textit{minimum cut}). A \textit{minimum cut} $E'$ is a cut that has the minimum total capacity $\sum\limits_{e \in E'}c(e)$.
\\
\begin{center}
\input{cut.tex}
\end{center}

The red and the blue lines on the following graph show two possible cuts. The former has total capacity 4, while the latter 8. The red one defines a minimum cut for the graph. One should notice that removing all edges from the graph is also a cut, but of course it is out of our interest.

The notion of cut has several practical applications. For example, when communication is critical it is important to find the ``cut'' of your network, which is what lines one should remove in order to disconnect two points.


%Javier's part

\begin{theorem}
The capacity of the minimum cut equals the value of the maximum flow.
\end{theorem}

\begin{proof}
First, if we have a cut of certain capacity, it is obvious that we cannot pass a flow greater than the sum of the capacities of the cut edges, which is the capacity of the cut. This is true for every cut, and, therefore, the capacity of minimum cut is an upper bound of the maximum amount of flow that can be moved from the source to the sink.

Now we'll prove by contradiction that it's possible to construct a flow with the same cost as the minimum cut. Let us suppose that $F^{*}$ is the maximum flow in $G$ and its amount is smaller than the value of the minimum cut $c^{*}$. The fact that $F^{*}$ is the maximum flow means that the residual graph $G_{f}$ does not have an augmenting path from $s$ to $t$, otherwise we could use this augmenting path to increase the flow, contradicting the assumption that $F^{*}$ is the maximum flow. Because $G_{f}$ does not have an augmenting path from $s$ to $t$, we can define $S$ as the set of vertices reachable from the source $s$ in $G_{f}$, including $s$ itself, and $T$ as the set of remaining vertices, including the sink $t$.

\vspace*{-30pt}

\begin{center}
\input{cut-proof.tex}
\end{center}

\vspace*{-80pt}

%\begin{flushleft}
%COMMENT: I don't think we should add the notes for this figure and count it: we didn't do it before. 
%\textbf{Figure 1.} There is not residual capacity on the edges of $G$ that crosses the cut of the sets $S$ and $T$. 
%\end{flushleft}
 %COMMENT: I do not know what is "this is exactly a cut of $S$ and $T$", so just rewrote the sentences

 By the definition of these sets, all edges of $G$ between $S$ and $T$ have to be saturated in direction from $S$ to $T$, otherwise there would be an arc in residual graph $G_{f}$ from a vertex of $S$ to a vertex of $T$, contradicting the definition of $S$. These edges are depicted in red color at the figure above. We can see that they form a cut of $G$ into two subgraphs $S$ and $T$, since if we remove them the graph will be disconnected.
 
The total flow from $s$ to $t$ is exactly the sum of the flow across all of the edges of the cut. As all edges of the cut are saturated, hence the flow through each edge is equal to its capacity, and, thus, the total flow $F^*$ is equal to the capacity of the cut $c(S,T)$. But the maximum flow by assumption is less than the cost of minimum cut, and thus, less than the cost of any cut; a contradiction.
\end{proof}

The theorem holds, so the capacity of the minimum cut is equal to the value of the maximum flow. Besides, this theorem automatically implies that augmenting path algorithm gives an optimal solution. We won't analyse the complexity of that algorithm, as we will discuss now a more efficient algorithm. 

\subsection{Algorithm II (push-relabel)}

Obtaining the maximum flow in a network has been a well known problem in the research community that has been studied for almost 60 years. The vast majority of the work was concerning the improvement of the augmenting path algorithm. But in 1998 Andrew Goldberg suggested a totally different approach to this problem focusing on the vertices instead of the edges. His work was published in the Journal of the ACM (ACM Press).

\subparagraph{Idea} This algorithm is based on the notion of gravity. The basic idea is that each vertex has its own height and the flow flows in accordance with the heights of the vertices by the rule of gravity: from the highest vertex to the lowest one. It is known that there is only one vertex height function that results in the optimal flow. The aim of the algorithm is to find it.\\
 
% The source is always the highest vertex and the sink is the lowest.

Initially this algorithm was named the Gravity-flow algorithm, however nowadays it is known as the ``push-relabel'' algorithm.

\subparagraph{Basic algorithm description} The algorithm can be viewed as a gravity-assisted process. The source of the network will be in the highest position and all other vertices will be dangling below, with the sink in the lowest position. Gravity will move flow down from the source to the sink through edges. This algorithm will manipulate the heights of the vertices in order to control the direction of the flow across edges. To start, we will push as much flow as possible into the network, which is the sum of the capacity of the edges connected to the source. This creates an excess of flow in the neighbors of the source. The main purpose of the algorithm is to remove this excess of flow by moving the flow down towards the sink, or, if impossible, moving the excess back to the source. This can be done by controlling the heights of the vertices. \\

The push-relabel algorithm for network flow starts with a very high flow, which is in most of the cases ``illegal'', since not all flow inserted in the source is delivered to the sink. At each step the algorithm refines the previous invalid flow until we get a valid one, which will be the optimal. On the contrary, the augmenting paths algorithm starts with a zero flow and iterates until the optimal flow is reached, while in every step a valid flow is maintained. 

The push-relabel algorithm has two complementary actions:
\begin{itemize}
\item \texttt{push}: try to push as much excess flow as possible to a connected vertex which has lower height. It checks if extra flow can go down through non-saturated edges.
\item \texttt{relabel}: change the height of a vertex. It adjusts a graph to have the possibility to get rid of excess flow.
\end{itemize}

One can run those operations in any order which results in extreme flexibility. The initial idea was to devise a parallel algorithm, as augmenting paths algorithm is sequential by its definition. Essentially push-relabel algorithm creates more freedom of how the algorithm works, allowing to affect the efficiency by designing new methods for handling those operations. The current most efficient designs are complicated, so we will look at the basic variant first, prove that it works and analyse its complexity. Then we will consider a way to improve its efficiency.

\subsubsection*{Framework for the design} 

We will now define the general idea about how one can handle the \texttt{push} and \texttt{relabel} operations.

\begin{center}
\input{framework}
\end{center}

In the beginning, we will saturate the edges that are connected to the source by pushing as much flow as their aggregate capacity. By doing so we are setting an obvious upper bound on the maximum flow which equals with $C$ -- the capacity of the cut containing the edges from the source to its immediate neighbors. Now we will try to propagate this amount of flow through the graph, but because we pushed too much flow, some vertices may have an excess flow.
\\\\
\textbf{Definition} (\textit{excess flow}). The \textit{excess flow} in a vertex is defined as difference between incoming and outgoing flows.\\

The fact that some vertices have excess flow means that in those vertices the conservation condition is violated. Remember that the conservation states that the amount of flow entering each vertex equals the amount of outgoing flow (except from vertices $s$ and $t$). So, actually, during the execution of the algorithm we have an invalid flow, called \textit{preflow}.
\\\\
\textbf{Definition} (\textit{preflow}). A \textit{preflow} ($PF$) has the following characteristics:
\begin{enumerate}
\item[i.] It obeys the capacity constraints.
\item[ii.] It may not obey the conservation of the flow in all the vertices. So there may be some vertices with an excess flow.
\end{enumerate}

The excess flow represents an illegal state, thus the aim of the algorithm is to get rid of it in every single vertex. So at each step the flow will be invalid, until the moment when no vertex will have excess flow. Then the preflow becomes a valid flow which actually will be the optimal solution. 

\begin{wrapfigure}{l}{0.3\textwidth}
  \vspace{-30pt}
  \begin{center}
    \input{saturated.tex}
  \end{center}
  \vspace{-60pt}
\end{wrapfigure}

\vspace{10pt}
We can still use the residual graphs for performing the two operations, as it contains the information about current residual capacity of the edges in each direction.

As depicted in the figure on the left, after saturating the edge $(u,v)$ we need to add the reverse edge $(v,u)$ with twice the initial capacity. If in result vertex $v$ gets excess flow that cannot be propagated further, we need to raise this vertex to be able to push the flow backwards.

\vspace{50pt}
As we already mentioned, the \texttt{push} operation pushes an amount of flow through an edge. In order to use the operation \texttt{push(u,v)},  the following three conditions should be fulfilled:

\begin{enumerate}
\item[i.] the height of the vertex $u$ needs to be bigger than vertex $v$
\item[ii.] the arc $(u,v)$ must exist in the residual graph
\item[iii.] the vertex $u$ should have an excess of flow
\end{enumerate}

\subsubsection*{Algorithm summary}

 A high-level summary of the push-relabel algorithm is the following:

\begin{itemize}
\item push into the source (through its neighbor edges) the maximum capacity available
\item while there are vertices with an excess flow
	\begin{itemize}
	\item if there is a vertex where \texttt{push} can be applied, use \texttt{push}
	\item if not, use \texttt{relabel} to change the height of one of these vertices
	\end{itemize}
\end{itemize}


\end{document}